﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_100_IsSameTree
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MainProject
    {
        static void Main(string[] args)
        {
            //TreeNode treeNode = new TreeNode(3, new TreeNode(1, null, null), new TreeNode(2, null, null));
            TreeNode treeNode = new TreeNode(1, new TreeNode(2), new TreeNode(3));
            TreeNode treeNode1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
            //TreeNode treeNode1 = new TreeNode(3, new TreeNode(1, new TreeNode(3), null), new TreeNode(2, null, null));
            //TreeNode treeNode1 = new TreeNode(3, new TreeNode(1, new TreeNode(2,null,null), null), new TreeNode(2, null, null));
            //Console.WriteLine(IsPalindrome(0));
            Console.WriteLine(IsSameTree(treeNode, treeNode1));

            Console.ReadKey();
        }
        public static bool IsSameTree(TreeNode p, TreeNode q)
        {
            return GetMiddleValue(null, null);
        }

        /// <summary>
        /// 深度优先搜索
        /// </summary>
        /// <param name="treeNode1"></param>
        /// <param name="treeNode2"></param>
        /// <returns></returns>
        public static bool GetMiddleValue1(TreeNode treeNode1, TreeNode treeNode2)
        {
            if (treeNode1 == null && treeNode2 == null)
            {
                return true;
            }
            else if (treeNode1 != null && treeNode2 != null)
            {
                if (treeNode1.val!= treeNode2.val)
                {
                    return false;
                }
                return GetMiddleValue(treeNode1.left, treeNode2.left) && GetMiddleValue(treeNode1.right, treeNode2.right);
            }
            else
                return false;
        }

        /// <summary>
        /// 广度优先搜索
        /// </summary>
        /// <param name="treeNode1"></param>
        /// <param name="treeNode2"></param>
        /// <returns></returns>
        public static bool GetMiddleValue(TreeNode treeNode1, TreeNode treeNode2)
        {
            Queue<TreeNode> TreeNode1Que = new Queue<TreeNode>();
            Queue<TreeNode> TreeNode2Que = new Queue<TreeNode>();
            TreeNode1Que.Enqueue(treeNode1);
            TreeNode2Que.Enqueue(treeNode2);

            while (TreeNode1Que.Count == TreeNode2Que.Count)
            {
                if (TreeNode1Que.Count == 0)
                    return true;

                TreeNode tempTreeNode1 = TreeNode1Que.Dequeue();
                TreeNode tempTreeNode2 = TreeNode2Que.Dequeue();

                if (tempTreeNode1 == null && tempTreeNode2 == null)
                {
                    return true;
                }
                else if (tempTreeNode1 != null && tempTreeNode2 != null)
                {
                    if (tempTreeNode1.val != tempTreeNode2.val)
                    {
                        return false;
                    }
                }
                else
                {
                    return false;
                }


                if (tempTreeNode1.left != null && tempTreeNode2.left != null)
                {
                    TreeNode1Que.Enqueue(tempTreeNode1.left);
                    TreeNode2Que.Enqueue(tempTreeNode2.left);
                }
                else if (tempTreeNode1.left == null && tempTreeNode2.left == null)
                {
                    
                }
                else
                {
                    return false;
                }

                if (tempTreeNode1.right != null && tempTreeNode2.right != null)
                {
                    TreeNode1Que.Enqueue(tempTreeNode1.right);
                    TreeNode2Que.Enqueue(tempTreeNode2.right);
                }
                else if (tempTreeNode1.right == null && tempTreeNode2.right == null)
                {

                }
                else
                {
                    return false;
                }
            }
            return false;
        }
    }
}
